
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "comm.h"


/**
 * 摒除法
 */

// ==== common part ====

struct unit {
    unsigned char value;
    unsigned short backup;
};


static unsigned char input[9][9] = {
    {0, 5, 0, 7, 0, 0, 1, 0, 0},
    {0, 6, 0, 1, 0, 9, 0, 0, 0},
    {0, 0, 1, 0, 8, 0, 4, 0, 0},
    {0, 8, 0, 0, 0, 0, 0, 0, 0},
    {0, 7, 3, 0, 9, 0, 8, 1, 0},
    {0, 0, 0, 0, 0, 0, 0, 3, 0},
    {0, 0, 8, 0, 4, 0, 9, 0, 0},
    {0, 0, 0, 8, 0, 3, 0, 6, 0},
    {0, 0, 2, 0, 0, 6, 0, 4, 0}
};

static void print_map(unsigned char input[9][9])
{
    int i, j;

    for (i = 0; i < 9; ++i) {
        if (i % 3 == 0)
            printf("#===#===#===#===#===#===#===#===#===\n");
        else
            printf(" --- --- --- --- --- --- --- --- ---\n");

        for (j = 0; j < 9; ++j) {
            printf("%s %d ", j % 3 == 0 ? "/" : "|", input[i][j]);
        }
        printf("/\n");
    }
    printf("#===#===#===#===#===#===#===#===#===\n");
}

static void transfer2sudoku(unsigned char input[9][9], struct unit output[9][9])
{
    int i, j;

    memset(output, 0x0, sizeof(struct unit) * 9 * 9);

    for (i = 0; i < 9; ++i) {
        for (j = 0; j < 9; ++j) {
            output[i][j].value = input[i][j];
            output[i][j].backup = 0x1ff;
        }
    }
}

static void print_sudoku(struct unit sudoku[9][9])
{
    int i, j, g, h;

    for (i = 0; i < 9; ++i) {
        if (i % 3 == 0)
            printf("#=====#=====#=====#=====#=====#=====#=====#=====#=====\n");
        else
            printf(" ----- ----- ----- ----- ----- ----- ----- ----- -----\n");

        // sub-row
        for (h = 0; h < 3; ++h) {

            for (j = 0; j < 9; ++j) {

                if (sudoku[i][j].value != 0) {
                    if (h == 0)
                        printf("%s %d   ", j % 3 == 0 ? "/" : "|", sudoku[i][j].value);
                    else
                        printf("%s     ", j % 3 == 0 ? "/" : "|");
                }
                else {
                    printf("%s ", j % 3 == 0 ? "/" : "|");

                    for (g = 0; g < 3; ++g) {
                        if ((sudoku[i][j].backup & (1<<(h*3 + g))) == 0)
                            printf(" ");
                        else
                            printf("%d", h*3 + g + 1);
                    }

                    printf(" ");
                }
            }
            printf("/\n");
        }
    }
    printf("#=====#=====#=====#=====#=====#=====#=====#=====#=====\n");
}

static int calc_sudoku_value(struct unit sudoku[9][9])
{
    unsigned char i, j, n = 0;

    for (i = 0; i < 9; ++i) {
        for (j = 0; j < 9; ++j) {
            if (sudoku[i][j].value != 0)
                n++;
        }
    }
    return n;
}

static int check_sudoku_correct(struct unit sudoku[9][9])
{
    unsigned int w, i, j, n, m, first_r, first_c;

    // check row
    for (i = 0; i < 9; ++i) {
        w = 0x1ff;
        for (j = 0; j < 9; ++j) {
            w &= ~(1<<(sudoku[i][j].value-1));
            // tc_log("w %x [%d][%d] value %d", w, i, j, sudoku[i][j].value);
        }
        if (w != 0x0) {
            tc_log_err("row %d check failed %x", i, w);
            return -1;
        }
    }

    // check column
    for (j = 0; j < 9; ++j) {
        w = 0x1ff;
        for (i = 0; i < 9; ++i) {
            w &= ~(1<<(sudoku[i][j].value-1));
        }
        if (w != 0x0) {
            tc_log_err("column %d check failed", j);
            return -1;
        }
    }

    // check block
    for (i = 0; i < 3; ++i) {
        for (j = 0; j < 3; ++j) {
            first_r = i*3;
            first_c = j*3;

            w = 0x1ff;

            for (n = 0; n < 3; ++n) {
                for (m = 0; m < 3; ++m) {
                    w &= ~(1<<(sudoku[first_r+n][first_c+m].value-1));
                }
            }

            if (w != 0x0) {
                tc_log_err("block (%d:%d) check failed", first_r, first_c);
                return -1;
            }
        }
    }

    return 0;
}

// ==== algorithm part ====

void remove_in_row(struct unit sudoku[9][9])
{
    unsigned char i, j, n;

    for (i = 0; i < 9; ++i) {
        for (j = 0; j < 9; ++j) {
            if (sudoku[i][j].value == 0)
                continue;

            // tc_log("sudoku[%d][%d] value %d", i, j, sudoku[i][j].value);
            for (n = 0; n < 9; ++n) {
                // tc_log("sudoku[%d][%d].value %d", i, n, sudoku[i][n].value);
                if (sudoku[i][n].value == 0) {
                    sudoku[i][n].backup &= ~(1<<(sudoku[i][j].value-1));
                    // tc_log("sudoku[%d][%d].backup %x", i, n, sudoku[i][n].backup);
                }
            }
        }
    }
}

void remove_in_column(struct unit sudoku[9][9])
{
    unsigned char i, j, n;

    for (i = 0; i < 9; ++i) {
        for (j = 0; j < 9; ++j) {
            if (sudoku[j][i].value == 0)
                continue;

            // tc_log("sudoku[%d][%d] value %d", j, i, sudoku[j][i].value);
            for (n = 0; n < 9; ++n) {
                // tc_log("sudoku[%d][%d].value %d", n, i, sudoku[n][i].value);
                if (sudoku[n][i].value == 0) {
                    sudoku[n][i].backup &= ~(1<<(sudoku[j][i].value-1));
                    // tc_log("sudoku[%d][%d].backup %x", n, i, sudoku[n][i].backup);
                }
            }
        }
    }
}

void remove_in_block(struct unit sudoku[9][9])
{
    unsigned char i, j, n, m, k, h, first_r, first_c;

    for (i = 0; i < 3; ++i) {
        for (j = 0; j < 3; ++j) {
            first_r = i*3;
            first_c = j*3;

            for (n = 0; n < 3; ++n) {
                for (m = 0; m < 3; ++m) {
                    if (sudoku[first_r+n][first_c+m].value == 0)
                        continue;

                    for (k = 0; k < 3; ++k) {
                        for (h = 0; h < 3; ++h) {
                            if (sudoku[first_r+k][first_c+h].value == 0){
                                sudoku[first_r+k][first_c+h].backup &= ~(1<<(sudoku[first_r+n][first_c+m].value-1));
                            }
                        }
                    }
                }
            }
        }
    }
}

void find_unique_in_row(struct unit sudoku[9][9])
{
    unsigned char i, j, w, exist_flag, exist_cnt, exist_r, exist_c;

    for (i = 0; i < 9; ++i) {
        for (w = 0; w < 9; ++w) {
            exist_flag = 0;
            exist_cnt = 0;

            for (j = 0; j < 9; ++j) {
                // tc_log("sudoku[%d][%d] value %d backup %x w %d", i, j, sudoku[i][j].value, sudoku[i][j].backup, w+1);
                if (sudoku[i][j].value != 0) {
                    if (sudoku[i][j].value == (w+1)) {
                        exist_flag = !0;
                        break;
                    } else {
                        continue;
                    }
                }                

                if (((1<<w) & sudoku[i][j].backup) != 0) {
                    // tc_log("row %d: %d exist in sudoku[%d][%d]", i+1, w+1, i, j);
                    exist_cnt++;
                    exist_r = i;
                    exist_c = j;
                }
            }

            // print_sudoku(sudoku);

            // tc_log("row %d: %d exist_flag %d exist_cnt %d", i+1, w+1, exist_flag, exist_cnt);
            if (exist_flag == 0) {
                if (exist_cnt == 1) {
                    tc_log("row %d: %d exist_cnt %d", i+1, w+1, exist_cnt);
                    sudoku[exist_r][exist_c].value = w+1;
                }
            }
        }
    }
}

void find_unique_in_column(struct unit sudoku[9][9])
{
    unsigned char i, j, w, exist_flag, exist_cnt, exist_r, exist_c;

    for (j = 0; j < 9; ++j) {
        for (w = 0; w < 9; ++w) {
            exist_flag = 0;
            exist_cnt = 0;

            for (i = 0; i < 9; ++i) {
                // tc_log("sudoku[%d][%d] value %d backup %x w %d", i, j, sudoku[i][j].value, sudoku[i][j].backup, w+1);
                if (sudoku[i][j].value != 0) {
                    if (sudoku[i][j].value == (w+1)) {
                        exist_flag = !0;
                        break;
                    } else {
                        continue;
                    }
                }                

                if (((1<<w) & sudoku[i][j].backup) != 0) {
                    // tc_log("row %d: %d exist in sudoku[%d][%d]", i+1, w+1, i, j);
                    exist_cnt++;
                    exist_r = i;
                    exist_c = j;
                }
            }

            // print_sudoku(sudoku);

            // tc_log("row %d: %d exist_flag %d exist_cnt %d", i+1, w+1, exist_flag, exist_cnt);
            if (exist_flag == 0) {
                if (exist_cnt == 1) {
                    tc_log("column %d: %d exist_cnt %d", i+1, w+1, exist_cnt);
                    sudoku[exist_r][exist_c].value = w+1;
                }
            }
        }
    }
}

void find_unique_in_block(struct unit sudoku[9][9])
{
    unsigned char i, j, n, m, first_r, first_c, exist_r, exist_c, w, exist_flag, exist_cnt;

    for (i = 0; i < 3; ++i) {
        for (j = 0; j < 3; ++j) {
            first_r = i*3;
            first_c = j*3;

            for (w = 0; w < 9; ++w) {
                exist_flag = 0;
                exist_cnt = 0;

                for (n = 0; n < 3; ++n) {
                    for (m = 0; m < 3; ++m) {
                        // tc_log("[%d][%d] value %d backup 0x%x w %d", n, m, sudoku[first_r+n][first_c+m].value, sudoku[first_r+n][first_c+m].backup, w+1);
                        if (sudoku[first_r+n][first_c+m].value != 0) {
                            if (sudoku[first_r+n][first_c+m].value == (w+1)) {
                                exist_flag = !0;
                                goto back1;
                            } else {
                                continue;
                            }
                        }

                        if (((1<<w) & sudoku[first_r+n][first_c+m].backup) != 0) {
                            exist_cnt++;
                            exist_r = n;
                            exist_c = m;
                        }
                    }
                }
back1:
                // tc_log("block (%d:%d): %d exist_flag %d exist_cnt %d", first_r, first_c, w+1, exist_flag, exist_cnt);
                if (exist_flag == 0) {
                    if (exist_cnt == 1) {
                        tc_log("block (%d:%d): %d exist_cnt %d", first_r, first_c, w+1, exist_cnt);
                        sudoku[first_r+exist_r][first_c+exist_c].value = w+1;
                    }
                }
            }
        }
    }
}

int sudoku_refresh(struct unit sudoku[9][9])
{
    int value_cnt = 0, last_value_cnt;

    do {
        last_value_cnt = value_cnt;

        remove_in_row(sudoku);
        // tc_log("after remove_in_row");
        // print_sudoku(sudoku);

        remove_in_column(sudoku);
        // tc_log("after remove_in_column");
        // print_sudoku(sudoku);

        remove_in_block(sudoku);
        // tc_log("after remove_in_block");
        // print_sudoku(sudoku);

        find_unique_in_row(sudoku);
        // tc_log("after find_unique_in_row");
        // print_sudoku(sudoku);

        find_unique_in_column(sudoku);
        // tc_log("after find_unique_in_column");
        // print_sudoku(sudoku);

        find_unique_in_block(sudoku);
        // tc_log("after find_unique_in_block");
        print_sudoku(sudoku);

        value_cnt = calc_sudoku_value(sudoku); 
        tc_log("calc_sudoku_value %d", value_cnt);
        if (value_cnt == 81)
            break;

    } while (last_value_cnt != value_cnt);

    return value_cnt;
}

int sudoku_assume(struct unit sudoku[9][9], unsigned char *r, unsigned char *c, unsigned char *bak1, unsigned char *bak2)
{
    unsigned char i, j, w, backup[9], cnt;

    for (i = 0; i < 9; ++i) {
        for (j = 0; j < 9; ++j) {
            cnt = 0;
            for (w = 0; w < 9; ++w) {
                if (sudoku[i][j].value == 0) {
                    if ((sudoku[i][j].backup & (1<<w)) != 0)
                        backup[cnt++] = w+1;
                }
            }

            if (cnt == 2)  {
                *r = i;
                *c = j;
                *bak1 = backup[0];
                *bak2 = backup[1];
                tc_log("i %d j %d bak1 %d bak2 %d", i, j, backup[0], backup[1]);
                return 0;
            }
        }
    }
    return -1;
}

int sudoku_do(struct unit sudoku[9][9])
{
    struct unit snap[9][9];
    unsigned char i, row, column, backup[2];
    int value_cnt, ret;

    value_cnt = sudoku_refresh(sudoku);
    if (value_cnt != 81) {
        ret = sudoku_assume(sudoku, &row, &column, &backup[0], &backup[1]);
        if (ret < 0) {
            tc_log_err("sudoku_assume failed %d", ret);
        } else {
            tc_log("assume row %d column %d backup[0] %d backup[1] %d", row, column, backup[0], backup[1]);

            for (i = 0; i < 2; ++i) {
                memcpy(snap, sudoku, sizeof(struct unit) * 9 * 9);
                snap[row][column].value = backup[i];

                tc_log("try assume [%d][%d] %d", row, column, backup[i]);
                ret = sudoku_do(snap);
                tc_log("sudoku_do ret %d assume [%d][%d] %d %s", ret, row, column, backup[i], ret == 0 ? "success" : "failed");
                if (ret == 0) {
                    memcpy(sudoku, snap, sizeof(struct unit) * 9 * 9);
                    return ret;
                }
            }
        }
    } else {
        ret = check_sudoku_correct(sudoku);
    }

    return ret;
}

int main(int argc, char const *argv[])
{
    struct unit sudoku[9][9];
    int ret;

    tc_log("********************");
    tc_log("new start @ %s %s", __DATE__, __TIME__);
    tc_log("********************");

    print_map(input);
    transfer2sudoku(input, sudoku);
    print_sudoku(sudoku);

    sudoku_do(sudoku);

    ret = check_sudoku_correct(sudoku);
    tc_log("check_sudoku_correct ret %d", ret);

    tc_log("exit");
    return 0;
}

